package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

public class _2_Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 1;
        dp[0][1] = 1;
        int maxLen = 1;
        int maxLenCnt = 1;
        for (int i = 1; i < n; i++) {
            int tempMaxLen = 0;
            int tempMaxLenCnt = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j][0] > tempMaxLen) {
                        tempMaxLen = dp[j][0];
                        tempMaxLenCnt = dp[j][1];
                    } else if (dp[j][0] == tempMaxLen) {
                        tempMaxLenCnt+=dp[j][1];
                    }
                }
            }
            tempMaxLen+=1;
            tempMaxLenCnt = tempMaxLenCnt == 0 ? 1 : tempMaxLenCnt;
            dp[i][0] = tempMaxLen;
            dp[i][1] = tempMaxLenCnt;
            if (tempMaxLen > maxLen) {
                maxLen = tempMaxLen;
                maxLenCnt = tempMaxLenCnt;
            } else if (tempMaxLen == maxLen) {
                maxLenCnt+=tempMaxLenCnt;
            }
        }
        return maxLenCnt;
    }

    @Test
    public void test(){
        int[] ints = {1,3,5,4,7};
        ints = new int[]{1,1,1,1,1};
//        ints = new int[]{1,2,4,3,5,4,7,2};
        System.out.println(findNumberOfLIS(ints));
    }
}
